/*
 * @lc app=leetcode.cn id=435 lang=cpp
 *
 * [435] 无重叠区间
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // auto compare = [](vector<int>& left, vector<int>& right)->bool{
        //     if (left[0]==right[0]){
        //         return left[1]<right[1];
        //     }else{
        //         return left[0]<right[0];
        //     }

        //     // return left[0]<right[0];
        //     // if (left[0]<right[0]){return false;}
        //     // else if (left[0]>right[0]){return true;}
        //     // else{
        //     //     return left[1]<right[1];
        //     // }
        // };
        // if (intervals.size()==1){return 0;}
        // sort(intervals.begin(), intervals.end(), compare);
        // int result = 0;
        // int end = intervals[0][1];
        // for (int i=1;i<intervals.size();i++){
        //     if (intervals[i][0]>=end){
        //         end = intervals[i][1];
        //     }else{
        //         result++;
        //     }
        // }
        // return result;
// if (intervals.empty()) {
// return 0;
// }
// int n = intervals.size();
// sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) {
// return a[1] < b[1];
// });
// int total = 0, prev = intervals[0][1];
// for (int i = 1; i < n; ++i) {
// if (intervals[i][0] < prev) {
// ++total;
// } else {
// prev = intervals[i][1];
// }
// }
// return total;

                if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1; // 记录非交叉区间的个数
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.size() - count;
    }
        static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
};
// @lc code=end

